The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We present a universal algebraic framework for rewriting terms and types over an arbitrary equational specification of types and typed combinators. Equational type specifications and their initial algebra semantics were introduced in Meinke [1991b]. For an arbitrary equational type specification (ɛ, E) we prove that the corresponding rewriting relation $$R\underrightarrow {(\varepsilon ,E)}*$$...
The usual definition of context as “a term with a hole” does not properly address the problems of applying rewrite rules to a context and is in particular inadequate in several respects when a context contains variable bindings. We claim that viewing TRSs as (free) preorder-enriched categories provides a smoother concept of context: on the one hand it allows to decompose a reduction step into redex...
In this paper we consider rewrite systems that describe the λ-calculus enriched with recursive and non-recursive local definitions by generalizing the lsexplicit substitutions’ used by Abadi, Cardelli, Curien, and Lévy [1] to describe sharing in λ-terms. This leads to ‘explicit cyclic substitutions’ that can describe the mutual sharing of local recursive definitions. We demonstrate how this may be...
A methodology Tor polymorphic type inference for general term graph rewriting systems is presented. This requires modified notions of type and of type inference due to the absence of structural induction over graphs. Induction over terms is replaced by dataflow analysis.
We introduce and study the notion of an equational definition over a predefined algebra (EDPA) which is a modification of the notion of an algebraic specification enrichment. We argue that the latter is not quite appropriate when dealing with partial functions (in particular, with those defined by non-terminating functional programs), and suggest EDPA as a more adequate tool for specification and...
In this paper we extend the recent divide and conquer technique of Middeldorp and Toyama for establishing (semi-)completeness of constructor systems to conditional constructor systems. We show that both completeness (i.e. the combination of confluence and strong normalization) and semi-completeness (confluence plus weak normalization) are decomposable properties of conditional constructor systems...
Collapsed trees are (hyper)graphs which represent functional expressions such that common subexpressions can be shared. Rewrite steps with collapsed trees include applications of term rewrite rules as well as “folding steps” which identify common subexpressions. Different aspects of this model of computation are considered: (1) It is shown that collapsed tree rewriting is complete with respect to...
A conditional term rewriting system (CTRS) is called simplifying if there exists a simplification ordering > on terms such that the left-hand side of any rewrite rule is greater than the right-hand side and the terms occurring in the conditions of that rule. If a simplifying join CTRS consists of finitely many rules, it is terminating and the applicability of a rewrite rule is decidable by recursively...
Recently we have shown the following abstract result for unconditional term rewriting systems (TRSs). Whenever the disjoint union R1 ⊕ R2 of two (finite) terminating TRSs R1, R2 is non-terminating, then one of the systems, say R1,...
We consider the termination problem of combinations of term-rewriting systems and the λ-calculus employing standard methods of the theory of term rewriting systems in contrast to (extensions of) Tait-Girard's technique. In particular for some class of higher-order rule systems, we explicitly construct a well-founded ordering over λ-terms whose combination with the β-reduction is terminating. Then,...
A property of many-sorted term rewriting systems is called persistent if it is not affected by removing the corresponding typing restriction. Persistency turns out to be a generalization of direct sum modularity. It is a more powerful tool for proving confluence and normalization properties. Strong normalization is persistent for the class of term rewriting systems for which not both duplicating rules...
We investigate how to prove termination of term rewriting systems by interpretation of terms. This can be considered as a generalization of polynomial interpretations. A classification of types of termination is proposed built on properties in the semantic level. A transformation on term rewriting systems eliminating distributive rules is introduced. Using this distribution elimination a new termination...
We show that a simple, and easily implementable, restriction on the recursive path ordering, which we call the “binary path condition”, suffices for establishing termination of extended rewriting modulo associativity and commutativity.
We summarize a number of new results concerning inductive-theorem proving in the area of design specifications using Horn logic with equality. Induction is explicit here because induction orderings must be integrated into the specification. However, the proofs need less guidance if the specification is ground confluent and strongly terminating. Calculi for verifying these conditions are presented...
We present a constructor-based approach for assigning appropriate semantics to algebraic specifications given by finite sets of positive/negative-conditional equations. Under the assumption of confluence of the reduction relation we define, the factor algebra of the ground term algebra modulo the congruence of this reduction relation is a minimal model which is (beyond that) the minimum of all models...
We present two approaches to define the semantics for positive/negative conditional rewrite systems. The first — the recursive evaluation approach — is based on a well-founded ordering and leads to a perfect model semantics. The second — the built-in evaluation approach — is based on a set of predefined inequations and leads to an initial model semantics provided the inequations are interpreted in...
We show how the method of proof by consistency can be extended to proving properties of the perfect model of a set of first-order clauses with equality. Technically proofs by consistency will be similar to proofs by case analysis over the term structure. As our method also allows to prove sufficient-completeness of function definitions in parallel with proving an inductive theorem we need not distinguish...
We have outlined a completion procedure for first-order clausal reasoning with inspiration from completion procedures for equational reasoning. We believe this to be a useful method for many practical applications involving clausal reasoning where the theory stays constant and is used repeatedly for proving many goals. Program synthesis (see [3]) is such an application. We have implemented a prototype...
We survey some basic issues in first-order theorem proving and their implications for conditional term-rewriting systems. In particular, we discuss the propositional efficiency of theorem proving strategies, goal-sensitivity, and the use of semantics. We give several recommendations for theorem proving strategies to enable them to properly treat these issues. Although few current theorem provers implement...
We study language-theoretical properties of the set of reducible ground terms with respect to a given rewriting system. As a tool for our analysis we introduce the property of finite irreducibility of a term with respect to a variable and prove it to be decidable. It turns out that this property generalizes numerous interesting properties of the language of ground normal forms. In particular, we show...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.